package 剑指II;

import 链表.ListNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-08
 **/

public class Jz026重排链表 {

    /**
     * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
     *  L0 → L1 → … → Ln-1 → Ln 
     * 请将其重新排列后变为：
     * L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
     * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     * <p>
     * 示例 1:
     * 输入: head = [1,2,3,4]
     * 输出: [1,4,2,3]
     * 示例 2:
     * 输入: head = [1,2,3,4,5]
     * 输出: [1,5,2,4,3]
     *  
     * 提示：
     * 链表的长度范围为 [1, 5 * 104]
     * 1 <= node.val <= 1000
     *  
     * 注意：本题与主站 143 题相同：https://leetcode-cn.com/problems/reorder-list/ 
     */

    public void reorderList(ListNode head) {
        Deque<ListNode> deque = new ArrayDeque<>();
        ListNode cur = head;
        while (cur != null) {
            deque.addLast(cur);
            cur = cur.next;
        }

        ListNode temp = new ListNode(-1);
        ListNode lastNode = temp;
        while (deque.size() > 1) {
            ListNode listNode1 = deque.removeFirst();
            ListNode listNode2 = deque.removeLast();
            lastNode.next = listNode1;
            listNode1.next = listNode2;
            lastNode = listNode2;
        }
        lastNode.next = null;
        if (deque.size() > 0) {
            ListNode listNode = deque.removeFirst();
            listNode.next = null;
            lastNode.next = listNode;
        }
        temp.next = null;
    }

}
